public class Test2 {
    /**
     * 算不出来
     * @param nums
     * @return
     */
    public int firstMissingPositive1(int[] nums) {
        int min = 0x3f3f3f3f, max = 1;
        long sum = 0L;
        for (int n : nums) {
            if (n >= 1) {
                sum += n;
                min = Math.min(min,n);
                max = Math.max(max,n);
            }
        }
        long ret = calculateSum(min,max);
        if (min > 1) return 1;
        return (int)(ret - sum == 0 ? (min == 1 ? max + 1 : min - 1) : ret - sum);
    }

    private long calculateSum(int start, int end) {
        long ret = 0L;
        for (int i = start; i <= end; i++) {
            ret += i;
        }
        return ret;
    }

    /**
     * 解决这道题目的关键就是需要知道这个没有出现的最小的正整数一定在[1,n+1]之间 n是数组长度
     * 一：所以我们可以先遍历一遍数组，将不在[1,n+]之间数字置换为n+1，也就是没有意义的数字
     * 二：然后剩下的数组中的元素就是在[1,n]之间的数字了，那么此时使用原地哈希的算法
     * 通过 int num = Math.abs(nums[i]),nums[num-1] = -Math.abs(nums[num-1])
     * 这里使用绝对值是为了避免数组中出现重复的元素，然后重复标记,同时也是为了避免因为前面便利的时候将后面的
     * [1,n]之间的元素修改成为负数，导致后面元素无法统计的情况
     * 三：统计第一个为正数的元素，那么缺失的第一个正数就是i+1
     * 四：如果所有元素都出现了，那么结果就是n+1
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 将所有不在范围内的数置为 n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // 利用数组的索引标记出现的数字
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 找到第一个正数对应的索引
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // 如果所有数字都正确，返回 n+1
        return n + 1;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        int[] arr = {7,8,9,11,12};
        test2.firstMissingPositive(arr);
        System.out.println(66);
    }
}
